import java.util.Arrays;
import java.util.Scanner;

public class Main {
    //冒泡排序
    /*public static  void func(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }*/

    //直接插入排序
    /*public static void insertSort(int[] array) {
        //i下标从第二个元素开始
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];//tmp存放i下标的值
            int j = i - 1;//j 指向i的前驱
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    //此时将j下标的值放到j的后驱位置
                    array[j + 1] = array[j];
                } else {
                    //此时是j下标的值较小
                    break;
                }
            }
            //此时j下标的值是负数了
            array[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }*/

    //冒泡排序练习
    /*public static void func(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    //交换
                    swap(array, j, j + 1);
                    //int tmp = array[j];
                    //array[j] = array[j + 1];
                    //array[j + 1] = tmp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }*/

    //交换的方法
    public static void swap(int[] array, int x, int y) {
            int tmp = array[x];
            array[x] = array[y];
            array[y] = tmp;
    }

    //直接插入排序练习
    /*public static void insertSort(int[] array) {
        //i下标从第二个元素开始
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            //j下标从i的前驱开始
            int j = i - 1;
            //j遍历数据
            for (; j >= 0; j--) {
                //如果j的值大于tmp下标的值就将j下标指向j的后继
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    //不大于就跳出 -  //此时j下标的值较小
                    break;
                }
            }
           //此时j下标的值是负数了
            array[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }*/

    //希尔排序练习
    /*public static void shellSort(int[] array) {
        //求数组长度
        int gap = array.length;//为10
        //分组
        while (gap > 1) {
            gap /= 2;//5组、2组、1组
            //调用直接插入排序
            insertSort(array, gap);
        }
        System.out.println(Arrays.toString(array));
    }

    //希尔排序的直接插入排序写法
    public static void insertSort(int[] array, int gap) {
        //i下标从gap位置开始
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            //j下标从i减gap个位置开始
            int j = i - gap;
            //j遍历数据
            for (; j >= 0; j-=gap) {
                //如果j下标的值大于tmp的值 - 将j的值给j的后继
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    //j的值较小
                    break;//跳出
                }
            }
            //此时j下标为负数
            array[j + gap] = tmp;//tmp的值给j+1下标位置
        }
    }*/

    //直接插入排序练习
    /*public static void insertSort(int[] array) {
        //i下标从数组的第二个位置开始
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            //j下标指向i的前驱
            int j = i - 1;
            for (; j >= 0; j--) {
                //j遍历数组
                if(array[j] > tmp) {
                    //将j下标的值放到j+1的位置中
                    array[j + 1] = array[j];
                } else {
                    break;//跳出
                }
            }
            //此时j指向了负数下标
            array[j + 1] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }

    //冒泡排序练习
    public static void func(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

    //希尔排序练习
    public static void shellSort(int[] array) {
        int gap = array.length;//数组的长度就是一开始分的组数
        //分组
        while (gap > 1) {
            gap /= 2;
            //调用直接插入排序
            insertSortshell(array, gap);
        }
        System.out.println(Arrays.toString(array));
    }

    //希尔排序的插入排序
    public static void insertSortshell(int[] array, int gap) {
        //i小标从gap位置开始
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            //j下标从i减去gap位置开始遍历数组
            int j = i - gap;
            for (; j >= 0; i -= gap) {
                if (array[j] > tmp) {
                    //j下标的值较大
                    array[j + gap] = array[j];
                } else {
                    break;
                }
            }
            //此时j下标的值为负数了
            array[j + gap] = tmp;
        }
    }*/

    //分解的方法
    /*public static void mergeSortChild(int[] array, int left, int right) {
        //分解
        if (left == right) {
            return;
        }
        int mid = (left + right) / 2;//中间位置
        mergeSortChild(array, left, mid);//递归1分解左边
        mergeSortChild(array, mid + 1, right);//递归右边
        //开始合并
        mergre(array, left, mid, right);
    }*/

    //合并的方法
    /*public static void mergre(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个数组
        int[] tmpArr = new int[right - left + 1];
        int k = 0;//记录数组下标
        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] <= array[s2]) {
                //数组下标加1个 指向下一个
                tmpArr[k++] = array[s1++];
            }else {
                //这是s2小的情况 -将s2的值放到数组中
                tmpArr[k++] = array[s2++];
            }
        }
        //此时是s1或者s2超出区间范围了，但是有可能有一个还未超出范围
        while (s1 <= e1) {
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArr[k++] = array[s2++];
        }
        //此时数组中的数据是有序的了 - 此时要将排序好的数组传到原来的数组中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArr[i];
        }
    }*/

    //递归实现归并排序练习
   /* public static void mergeSort(int[] array) {
        //调用分解方法
        mergeSortChild(array, 0, array.length - 1);
    }

    //分解的方法
    public static void mergeSortChild(int[] array, int left, int right) {
        //为空则说明分解完毕
        if (left == right) {
            return;
        }
        //为分解完毕的情况
        int mid = (left + right) / 2;//求待分解数组中位置的下标
        //递归分解左边和右边
        mergeSortChild(array, left, mid);//分解左边
        mergeSortChild(array, mid + 1, right);//分解右边
        //分解完毕 - 调用方法开始合并
        mergre(array, left, mid, right);
    }

    //合并的方法
    public static void mergre(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //定义一个长度是两组数据之和的数组
        int[] tmpArray = new int[right - left + 1];
        //遍历数据
        int k = 0;//用来遍历合并后的数组
        while (s1 <= e1 && s2 <= e2) {
            //比较s1和s2哪个值较大
            if (array[s1] > array[s2]) {
                //将s2值放到合并后的数组里并且将较小的s2往后走一个位置
                tmpArray[k++] = array[s2++];
            } else {
                //较小的是s1
                tmpArray[k++] = array[s1++];
            }
        }
        //s1超出区间时，s2可能还未超过
        while (s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }
        //s2超出区间时，s1可能还未超过
        while (s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        //此时合并完成,将合并后的数组放到原来的数组中
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArray[i];
        }
    }*/

    //递归实现归并排序练习
    public static void mergeSort(int[] array) {
        mergeSortChild(array, 0, array.length - 1);//调用分解方法
    }

    //分解的方法
    public static void mergeSortChild(int[] array, int left,  int right) {
        if (left == right) {
            return;
        }
        //不等于的情况
        int mid = (left + right) / 2;//求中间位置
        //递归分解
        mergeSortChild(array, left, mid);//分解左边
        mergeSortChild(array, mid + 1, right);//分解右边
        //此时开始合并
        mergr(array, left, mid, right);//调用合并方法
    }

    //合并的方法
    public static void mergr(int[] array, int left, int mid, int right) {
        //获得两组数据收尾位置
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int k = 0;//记录新数组下标
        int[] tmpArray = new int[right - left + 1];
        while (s1 <= e1 && s2 <= e2) {
            //未超过区间
            if (array[s1] > array[s2]) {
                //将较小的s2给一个新数组后往后走一个位置。
                tmpArray[k++] = array[s2++];
            } else {
                //此时较小的是s1
                tmpArray[k++] = array[s1++];
            }
        }
        //s1超过区间时，s2可能未超过
        while (s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }
        //s2超过区间时，s1可能未超过
        while (s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        //此时将排序好的数组放到原数组即可
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArray[i];
        }
    }

    //非递归实现归并排序练习
    /*public static void isNotNotRecursiveMergeSort(int[] array) {
        int gap = 1;//先假定每一个数都是单独有序的
        while (gap < array.length) {
            for (int i = 0; i < array.length; i+=gap * 2 ) {
                int left = i;//左边是i下标的位置
                int mid = left + gap - 1;//中间的位置
                int right = gap + mid;
                //防止right和mid越界
                if(mid >= array.length) {
                    mid = array.length - 1;//放到新位置
                }
                if(right >= array.length) {
                    right = array.length - 1;//放到新位置
                }
                //开始归并 - 调用之前的合并方法
                mergr(array, left, mid, right);
            }
            gap *= 2;
        }
    }*/

    //非递归实现归并排序练习
    public static void isNotNotRecursiveMergeSort(int[] array) {
        int gap = 1;//假设每一个数都是单独有序的
        while (gap < array.length) {
            //再分成2个数数和4个数有序的
            for (int i = 0; i < array.length; i+= gap * 2) {
                int left = i;//为i下标
                int mid = left + gap - 1;//中间位置
                int right = gap + mid;
                //防止mid和right越界
                if (mid >= array.length) {
                    //重新直向位置
                    mid = array.length - 1;
                }
                if (right >= array.length) {
                    right = array.length - 1;
                }
                //调用合并方法
                mergr(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    //计数排序练习
    public static void countSort(int[] array) {
        //遍历数组找到最大值和最小值 - 找到才能确定数组的长度
        int maxVal = array[0];//假设最大值在0下标
        int minVal = array[0];//假设最小值在0下标
        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                //此时i下标的值为最大值
                maxVal = array[i];
            }
            if (array[i] < minVal) {
                //此时i下标为最小值
                minVal = array[i];
            }
        }
        //确定数组的长度
        int len = maxVal - minVal + 1;
        int[] countArr = new int[len];
        //遍历数组统计每个数字出现的次数
        for (int i = 0; i < array.length; i++) {
            int val = array[i];
            countArr[val - minVal] ++;
        }
        int index = 0;
        //此时计数完毕 - 看每个下标的值是几就打印几
        for (int i = 0; i < countArr.length; i++) {
            while (countArr[i] > 0) {
                array[index] = i + minVal;
                index++;
                countArr[i]--;
            }
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            int num = input.nextInt();
            array[i] = num;
        }
        //isNotNotRecursiveMergeSort(array);
        //System.out.println("非递归归并排序后" + Arrays.toString(array));
        countSort(array);
        System.out.println("计数排序后" + Arrays.toString(array));
    }

    public static void main3(String[] args) {
        Scanner input = new Scanner(System.in);
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            int num = input.nextInt();
            array[i] = num;
        }
        mergeSort(array);
        System.out.println("归并排序后" + Arrays.toString(array));
    }

    public static void main2(String[] args) {
        int[] array = {10,9,8,7,6,5,4,3,2,1,0};
        //insertSort(array);
        //shellSort(array);
    }

    public static void main1(String[] args) {
        int[] array = {10,9,8,7,6,5,4,3,2,1};
        //func(array);
        //insertSort(array);
        //shellSort(array);//测试希尔排序
    }
}
